package tiltmaze.solver;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import tiltmaze.Maze;

/**
 * Class used for finding solutions of a maze.
 * WARNING no more than 30 checkpoints allowed (overflow)
 * @author Juraj Nižnan
 */
public class MazeSolver {

    private Maze maze;
    private HashSet<MazePath> paths = new HashSet<MazePath>();
    ArrayList<MazePath> endedPaths = new ArrayList<MazePath>();
    HashSet<MazePath> visitedPaths = new HashSet<MazePath>();
    private boolean finishedSolving = false;
    private int longestPath = 0;
    private int shortestSolution = 0;
    private long time = 0;
    MazeMotionGraph motion;
    MazeStatesInterface stateGraph;

    public MazeSolver(Maze maze) {
        this.maze = maze;
    }

    /**
     * solves by BFS
     */
    public void solve() {
        long time1 = System.currentTimeMillis();
        motion = new MazeMotionGraph(maze);
        MazePath p = new MazePath();
        p.lastVertex = motion.start;
        paths.add(p);
        visitedPaths.add(p);
        if (stateGraph != null) {
            stateGraph.addStartNode(p);
        }
        while (!paths.isEmpty()) {
            nextStep();
            longestPath++;
        }
        finishedSolving = true;
        long time2 = System.currentTimeMillis();
        time = time2 - time1;
    }

    private void nextStep() {
        HashSet<MazePath> paths1 = new HashSet<MazePath>();
        for (MazePath path : paths) {
            for (int i = 0; i < 4; i++) {
                if (path.lastVertex.targets[i] != null) {
                    MazePath path1 = new MazePath();
                    path1.lastVertex = path.lastVertex.targets[i];
                    path1.path = new ArrayList<Integer>(Collections.unmodifiableList(path.path));
                    path1.path.add(i);
                    path1.checkpointsCollected = path.checkpointsCollected | path.lastVertex.edges[i];
                    if (!visitedPaths.contains(path1)) {
                        visitedPaths.add(path1);
                        boolean ended1 = ended(path1);
                        if (ended1) {
                            shortestSolution = (shortestSolution == 0) ? longestPath + 1 : shortestSolution;
                            endedPaths.add(path1);
                        } else {
                            paths1.add(path1);
                        }
                        if (stateGraph != null) {
                            stateGraph.addNode(path1, ended1);
                        }
                    }
                    if (stateGraph != null) {
                        stateGraph.addEdge(path, path1, i);
                    }
                }
            }
        }
        paths = paths1;
    }

    boolean ended(MazePath path) {
        return path.checkpointsCollected + 1 >= exp(maze.getNumOfCheckpoints());
    }

    public int getLongestPathLength() {
        if (!finishedSolving) {
            solve();
        }
        return longestPath;
    }

    public int getShortestSolutionLength() {
        if (!finishedSolving) {
            solve();
        }
        return shortestSolution;
    }

    public String getPaths() {
        String ret = "";
        for (MazePath path : endedPaths) {
            ret += path.toString() + "\n";
        }
        return ret;
    }

    public int getNumOfSols() {
        if (!finishedSolving) {
            solve();
        }
        return endedPaths.size();
    }

    public int getNumOfVisitedStates() {
        if (!finishedSolving) {
            solve();
        }
        return visitedPaths.size();
    }

    public long getTime() {
        if (!finishedSolving) {
            solve();
        }
        return time;
    }

    public static int exp(int a) {
        int ret = 1;
        for (int i = 0; i < a; i++) {
            ret = ret * 2;
        }
        return ret;
    }
}
